import java.util.Arrays;

public class Solution410 {
    public int splitArray(int[] nums, int m) {
        int l=Arrays.stream(nums).max().getAsInt(),r= Arrays.stream(nums).sum();
        int ans=Integer.MAX_VALUE;
        while (l<=r){
            int mid=(l+r)/2;
            int cur=0,num=1;
            for (int i=0;i<nums.length;i++){
                if (cur+nums[i]>mid){
                    num++;
                    cur=nums[i];
                }else{
                    cur=cur+nums[i];
                }
            }
            if (num<=m){
                ans=Math.min(ans,mid);
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution410().splitArray(new int[]{7,2,5,10,8},2));
    }
}
